Explication du problème en grandes LIGNES:
La notation polonaise inverse (NPI) (en anglais RPN pour Reverse Polish Notation) permet d'écrire de façon non ambiguë les formules arithmétiques sans utiliser de parenthèses.
Par exemple, l’expression « 3 × (4 + 7) » peut s'écrire en NPI sous la forme : « 4 7 + 3 × ». On doit donc avoir une structure de données qui stocke les entrées de l'utilisateur et récupérer les dernières entrées. La pile est parfaite pour cette tâche. En effet, les opérations pour empiler ces entrées et les dépiler se font en temps constant.
L'algorithme :
D'abord, on sépare l'expression pour avoir un tableau de chaque élément. Ensuite, on parcours ce tableau. Pour chaque élément, on empile dans une pile, qu'on aura créée, si l'élément est n'est pas une opération. Si c'est une opération, on la fait avec les 2 derniers éléments entrés, si impossible on affiche une erreur. On empile la valeur obtenue dans la pile.
class Maillon:
def __init__(self, valeur, suivant = None):
self.valeur = valeur
self.suivant = suivant
class PileOptim:
def __init__(self, tete = None):
self.tete = tete
def est_vide(self):
return self.tete is None
def empiler(self, valeur):
self.tete = Maillon(valeur,self.tete)
def depiler(self):
assert not self.est_vide(), 'Pile vide'
val_depile = self.tete.valeur
self.tete = self.tete.suivant
return val_depile
def __str__(self):
if self.est_vide():
return '[]'
liste_chaine = ''
maillon = self.tete
while maillon.suivant is not None:
liste_chaine += str(maillon.valeur) + ', '
maillon = maillon.suivant
liste_chaine += str(maillon.valeur)
return '['+liste_chaine+']'
def NPI(exp):
"""
Fonction qui renvoie le resultat de l'espression exp qui est adapte au calcul NPI
parametre : une chaîne contenant les opérandes et opérateurs d'une expression en NPI (str)
sortie : resultat de l'expression sous forme int
"""
pile = PileOptim()
expression = exp.split(' ')
for el in expression:
assert el.isdigit() or el in '*+-/', 'Expression incorrecte, on attend que des nombres ou operations'
if not el in '*+-/': # cas ou c'est un nombre
pile.empiler(int(el))
else: # cas ou c'est une operation a faire
assert not pile.est_vide(), 'Expression incorrecte : on ne peut pas faire des operation sans nombres'
val2 = pile.depiler()
assert not pile.est_vide(), 'Expression incorrecte on ne peut pas faire des operation avec 1 seul nombre'
val1 = pile.depiler()
if el == '+': # addition
pile.empiler(val1+val2)
elif el == '*': # multiplication
pile.empiler(val1*val2)
elif el == '-': # soustraction
pile.empiler(val1-val2)
else: # division
assert val2 != 0, 'Division par 0 impossible'
pile.empiler(val1/val2)
resultat = pile.depiler(), " Expression incorrecte, 'il reste plus d'un nombre après les opérations"
assert pile.est_vide()
return resultat
if __name__ == '__main__':
exp = "3 10 2 - *"
print("Test de l'expression (10-2)*3 : ", NPI(exp))
print("Test de l'expression (6+2)*4-4 : ",NPI('2 6 + 4 * 4 -'))
print("Test de avec une expression incorrecte : ",NPI('2 + 4 * 4 -'))